import java.util.HashMap;
import java.util.Map;

public class LRUCache2 {

    class Node {
        private Integer key;
        private Integer val;
        private Node next;
        private Node pre;

        public Node(Integer key, Integer val) {
            this.key = key;
            this.val = val;
        }
    }

    private Map<Integer, Node> map = new HashMap<>();

    private Node head;

    private Node tail;

    private int capacity;

    public LRUCache2(int capacity) {
        this.capacity = capacity;
        head = new Node(null, null);
        tail = new Node(null, null);
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node != null) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            appendToTail(node);
            return node.val;
        }
        return -1;
    }

    private void appendToTail(Node node) {
        node.next = tail;
        node.pre = tail.pre;
        tail.pre.next = node;
        tail.pre = node;
    }

    public void set(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.val = value;
            map.put(key, node);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            appendToTail(node);
            return;
        }
        if (map.size() == capacity) {
            Node tmp = head.next;
            head.next = head.next.next;
            head.next.pre = head;
            map.remove(tmp.key);
        }
        Node newNode = new Node(key, value);
        appendToTail(newNode);
        map.put(key, newNode);
    }

}
